package 题目集.倍增算法.lca;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 货车运输 一共有n座城市，编号1 ~ n 一共有m条双向道路，每条道路(u, v, w)表示有一条限重为w，从u到v的双向道路
 * 从一点到另一点的路途中，汽车载重不能超过每一条道路的限重 每条查询(a, b)表示从a到b的路线中，汽车允许的最大载重是多少
 * 如果从a到b无法到达，那么认为答案是-1 一共有q条查询，返回答案数组 1 <= n <= 10^4 1 <= m <= 5 * 10^4 1 <= q
 * <= 3 * 10^4 0 <= w <= 10^5 1 <= u, v, a, b <= n 测试链接
 * https://www.acwing.com/problem/content/508/
 * https://www.luogu.com.cn/problem/P1967
 * 容易想到，需要生成一个最大边生成树。
 * 第一思路：先生成最小生成树，然后dfs查找a~b点，记录下载重的最小值。会爆栈
 * 优化：求a-b点路径上的最小值，相当于是a和b到最近公共祖先路径上的最小值。我们可以用一个st表维护其最小值
 *
 */
public class ch05_货车运输2_lca {

	static int[][] edges; // 存储所有的边，0：from,1:to。2:w
	static List<int[]>[] graph;
	static int n, m;
	static int maxn = (int) 1e4 + 10, maxm = (int) (5e4 + 10);
	static int[] p = new int[maxn], size = new int[maxn]; // 并查集的父集和大小
	static int[][] fa, st; // lca的父亲信息，以及最小值信息
	static int[] deep;
	static int power;
	static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

	public static void main(String[] args) {
		Reader sc = new Reader();
		n = sc.nextInt();
		m = sc.nextInt();
		graph = new List[n + 1];
		edges = new int[m][];
		for (int i = 1; i <= n; i++) {
			graph[i] = new ArrayList<>();
			p[i] = i;
			size[i] = 1;
		}
		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			edges[i] = new int[] { u, v, w };
		}
		List<int[]> result = kruskal();
		for (int[] edge : result) {
			graph[edge[0]].add(new int[] { edge[0], edge[1], edge[2] });
			graph[edge[1]].add(new int[] { edge[1], edge[0], edge[2] });
		}
		build();
		int q = sc.nextInt();
		for (int i = 0; i < q; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			if (find(u) != find(v)) {
				out.println(-1);
			} else {
				int res = query(u, v);
				out.println(res);
			}
		}
		out.flush();
	}

	/**
	 * 求a到b路径中的最小值
	 */
	public static int query(int a, int b) {
		// lca模板
		int high = deep[a] < deep[b] ? a : b;
		int low = deep[a] < deep[b] ? b : a;
		int min = Integer.MAX_VALUE;
		if (deep[high] != deep[low]) {
			for (int i = power - 1; i >= 0; i--) {
				if (deep[fa[low][i]] > deep[high]) {
					min = Math.min(min, st[low][i]);
					low = fa[low][i];
				}
			}
			min = Math.min(min, st[low][0]);
			low = fa[low][0];
		}
		if (low == high) {
			return min;
		}
		for (int i = power - 1; i >= 0; i--) {
			if (fa[low][i] != fa[high][i]) {
				//这行语句必须写在上升之前
				int curMin = Math.min(st[low][i], st[high][i]);
				min = Math.min(curMin, min);
				//上升
				low = fa[low][i];
				high = fa[high][i];
			}
		}
		int last = Math.min(st[low][0], st[high][0]);
		return Math.min(last, min);
	}

	/**
	 * acwing超时
	 */
	private static void build() {
		power = (int) Math.ceil(Math.log(n) / Math.log(2));
		fa = new int[n + 1][power];
		st = new int[n + 1][power];
		deep = new int[n + 1];
		boolean[] vis = new boolean[n + 1];
		for (int i = 1; i <= n; i++) {
			if (!vis[p[i]]) {
				vis[p[i]] = true;
				build(p[i]);
			}
		}
	}

	public static void build(int root) {
		level1(root);
		for (int p = 1; p < power; p++) {
			for (int i = 1; i <= n; i++) {
				fa[i][p] = fa[fa[i][p - 1]][p - 1];
				st[i][p] = Math.min(st[i][p - 1], st[fa[i][p - 1]][p - 1]);
			}
		}
	}

	static int[] q = new int[maxn];

	public static void level1(int root) {
		int h = 0, t = 0;
		q[t++] = root;
		st[root][0] = Integer.MAX_VALUE; // 到其父节点的最小值。根到根默认无穷大
		fa[root][0] = root;
		deep[root] = 0;
		while (h != t) {
			int cur = q[h++];
			for (int[] edge : graph[cur]) {
				int to = edge[1];
				if (to != fa[cur][0]) {
					q[t++] = to;
					fa[to][0] = cur;
					// 到父亲的最小值
					st[to][0] = edge[2];
					deep[to] = deep[cur] + 1;
				}
			}
		}
	}

	/**
	 * 返回最小生成树的所有关键边
	 */
	public static List<int[]> kruskal() {
		Arrays.sort(edges, (a, b) -> b[2] - a[2]);
		List<int[]> result = new ArrayList<>();
		for (int[] edge : edges) {
			int u = edge[0];
			int v = edge[1];
			if (find(u) != find(v)) {
				union(p[u], p[v]);
				result.add(edge);
			}
		}
		return result;
	}

	private static void union(int a, int b) {
		if (size[p[a]] > size[p[b]]) {
			size[p[a]] += size[p[b]];
			p[b] = p[a];
		} else {
			size[p[b]] += size[p[a]];
			p[a] = p[b];
		}
	}

	private static int find(int o) {
		return p[o] == o ? o : (p[o] = find(p[o]));
	}

	static class Reader {
		static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		public Reader(Object... o) {
		}

		public int nextInt() {
			try {
				in.nextToken();
			} catch (Exception ignored) {
			}
			return (int) in.nval;
		}
	}
}
